package com.mdnote.practice.devide_and_rule;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/16 多数元素
 * @description
 */
public class LeetCode169 {

    public static void main(String[] args) {
        LeetCode169 leetCode167 = new LeetCode169();
        int res = leetCode167.hashTable(new int[]{11, 22, 22, 44, 11, 11, 22, 11});
        System.out.println(res);

    }

    public int majorityElement(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // 哈希表
//        int res = hashTable(nums);
        // 递归
//        int rse = recursion(0, nums.length - 1, nums);
        // 投票
        int rse = vote(nums);
        return rse;
    }

    private int vote(int[] nums) {

        int condition = nums[0];
        int count = 0;

        for (int i = 0; i < nums.length; i++) {
            if (count == 0) {
                // 比如 11 11 11 11 22 22 22 22 11
                condition = nums[i];
            }
            if (nums[i] == condition) {
                count++;
            } else {
                count--;
            }
        }
        return condition;
    }

    private int recursion(int left, int right, int[] nums) {

        // Terminator，最终会被拆分到只有1个数
        if (left == right) {
            return nums[left];
        }
        // device big problem
        int leftRes = recursion(left, (left + right) / 2, nums);
        int rightRes = recursion((left + right) / 2, right, nums);
        // merge
        if (leftRes == rightRes) {
            return leftRes;
        } else {
            // 判断一下左边的众数是在右边的数量是否大于右边众数在左边的数量
            int leftCount = count((left + right) / 2, right, nums, leftRes);
            int rightCount = count(right, (left + right) / 2, nums, rightRes);
            return leftCount > rightCount ? leftRes : rightRes;
        }
        // restore current data

    }

    private int count(int left, int right, int[] nums, int num) {
        int count = 0;
        for (int i = left; i < right; i++) {
            if (nums[i] == num) {
                count++;
            }
        }
        return count;
    }

    private int hashTable(int[] nums) {

        if (nums.length == 1) {
            return nums[0];
        }

        Map<Integer, Integer> hashTable = new HashMap<>();


        for (int i = 0; i < nums.length; i++) {
            Integer temp = hashTable.get(nums[i]);
            if (temp == null) {
                hashTable.put(nums[i], 1);
            } else {
                hashTable.put(nums[i], temp + 1);
            }
        }
        int max = 0;
        int maxNum = 0;
        for (Map.Entry<Integer, Integer> entry : hashTable.entrySet()) {
            if (entry.getValue() > max) {
                max = entry.getValue();
                maxNum = entry.getKey();
            }
        }
        return maxNum;
    }
}
